#include <iostream>
using namespace std;

#define SIZE 13

/// @brief 值为-1表示为根节点，元素值为其父节点的数组下标
int UFSets[SIZE]; // 集合元素素组

// 初始化并查集
void Initial(int S[])
{
    for (int i = 0; i < SIZE; i++)
    {
        S[i] = -1;
    }
}

/// @brief Find"查"操作，找x所属集合（返回x所属根节点）
/// @param S
/// @param x
/// @return
int Find(int S[], int x)
{
    while (S[x] >= 0) // 循环寻找x的根
    {
        x = S[x];
    }
    return x; // 根的S[ ]小于0
}

/// @brief Union "并"操作，将两个集合合并为一个
/// @param S
/// @param Root1
/// @param Root2
void Union(int S[], int Root1, int Root2)
{
    // 要求Root1和Root2是不同的集合
    if (Root1 == Root2)
    {
        return;
    }
    // 将跟 Root2连接到另一根Root1下面
    S[Root2] = Root1;
}

//////////////////////////并查集的优化/////////////////////////////////////////////

/// @brief Find“查”操作优化，先找到根节点，再进行“压缩路径”
/// @param S
/// @param x
/// @return
int FindPro(int S[], int x)
{
    int root = x;
    while (S[root] >= 0)
    { // 循环找到根
        root = S[root];
    }
    while (x != root)
    {                 // 压缩路径
        int t = S[x]; // t指向x的父节点
        S[x] = root;  // x直接挂到根节点下
        x = t;
    }
    return root; // 返回根节点编号
}

/// @brief Union优化 “并”操作，小树合并到大树
/// @param S
/// @param Root1
/// @param Root2
void UnionPro(int S[], int Root1, int Root2)
{
    if (Root1 == Root2)
    {
        return;
    }
    if (S[Root2] > S[Root1])
    {                         // Root2节点数更少
        S[Root1] += S[Root2]; // 累加节点总数
        S[Root2] = Root1;     // 小树root2合并到大树root1
    }
    else
    {
        S[Root2] += S[Root1]; // 累加节点总数
        S[Root1] = Root2;     // 小树root1合并到大树root2
    }
}
